package string.compare;

/**
 * @Classname : LongestPalindromicSubstring
 * @Description : 5. 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * @Author : chentianyu
 * @Date 2022/12/20 23:06
 */


public class LongestPalindromicSubstring {

    /**
     * 动态规划
     *
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        int begin = 0, maxLen = 0, n = s.length();
        // dp[l][r] 表示字符串s的子串[l, r]是否为回文字符串
        boolean[][] dp = new boolean[n][n];
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r || (l + 1 == r && s.charAt(l) == s.charAt(r))) dp[l][r] = true;
                else dp[l][r] = dp[l + 1][r - 1] && s.charAt(l) == s.charAt(r);

                if (dp[l][r] && r - l + 1 > maxLen) {
                    begin = l;
                    maxLen = r - l + 1;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 遍历法
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        String sub = s.substring(0, 1);
        for (int i = 1; i < s.length(); i++) {
            sub = lengthOfCurentPosition(s, i, i, sub);
            sub = lengthOfCurentPosition(s, i - 1, i, sub);
        }
        return sub;
    }

    private String lengthOfCurentPosition(String s, int l, int r, String sub) {
        int len = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            if (l == r) len++;
            else len += 2;
            l--;
            r++;
        }
        if (len > sub.length()) {
            sub = s.substring(l + 1, r);
        }
        return sub;
    }
}
